/**
 * Created by jack on 18/4/1.
 现在这个方法没有测试通过，测试中花费的时间较多  52/63测试通过率
 */
public class DisSub {
    private int slength,tlength,ssubt;
    private int times = 0;
    private String s,t;
    public int numDistinct(String s, String t) {
        slength = s.length();
        tlength = t.length();
        ssubt = slength - tlength;
        if(ssubt < 0){
            return 0;
        }
        this.s = s;
        this.t = t;
        match(0,0,0,0);
        return times;
    }

    private void match(int sindex ,int tindex, int giveup, int mismatch){
        if(tindex >= tlength){
            this.times ++;
            return;
        }
        if(sindex >= slength){
            //不符合匹配的规则
            return ;
        }
        if(giveup + mismatch > ssubt){
            //不符合匹配规则，直接退出
            return ;
        }
        if(s.charAt(sindex) == t.charAt(tindex)){
            //两种选择  match   放弃
            //match
            match(sindex + 1, tindex + 1,giveup,mismatch);

            //放弃这次匹配
            match(sindex + 1,tindex ,giveup + 1,mismatch);
        }else{
            match(sindex + 1,tindex,giveup,mismatch + 1);
        }
    }
}
